from collections import deque
from typing import List


class Solution:
    def generatePermutation(self , s: str) -> List[str]:
        # write code here
        q = deque()
        ans = []
        dic = set()
        n = len(s)
        def process(i, q):
            if i == n:
                res = ''.join(q)
                if res not in dic:
                    ans.append(res)
                    dic.add(res)
            else:
                process(i + 1, q)
                q.append(s[i])
                process(i + 1, q)
                q.pop()
        process(0, q)
        return ans